package com.structure;

import lombok.NoArgsConstructor;

/**
 * @Author: Gallrax
 * @Description:
 * @Date: 2019/1/9
 */
public class BinaryTree {

    private BinaryNode root;

    public BinaryNode getRoot() {
        return root;
    }

    public BinaryNode find(int key) {
        if (root == null || root.key == key) {
            return root;
        }
        BinaryNode current = root;
        while (true) {
            if (current == null) {
                return null;
            }
            if (key < current.key) {
                current = current.leftNode;
            } else if (key > current.key) {
                current = current.rightNode;
            } else if (key == current.key) {
                return current;
            }
        }
    }

    public boolean insert(int key) {
        BinaryNode binaryNode = new BinaryNode(key);
        if (root == null) {
            root = binaryNode;
            return true;
        }
        BinaryNode parent = root;
        while (true) {
            if (key < parent.key) {
                if (parent.leftNode != null) {
                    parent = parent.leftNode;
                } else {
                    parent.leftNode = binaryNode;
                    return true;
                }
            } else {
                if (parent.rightNode != null) {
                    parent = parent.rightNode;
                } else {
                    parent.rightNode = binaryNode;
                    return true;
                }
            }
        }
    }

    public boolean delete(int key) {
        if (root != null) {
            return false;
        }
        BinaryNode current = root;
        BinaryNode parent = current;
        while (true) {
            parent = current;
            if (current == null) {
                return false;
            } else if (key < current.key) {
                if (current.leftNode != null) {
                    current = current.leftNode;
                } else {
                    return false;
                }
            } else if (key > current.key) {
                if (current.rightNode != null) {
                    current = current.rightNode;
                } else {
                    return false;
                }
            } else {
                //如果删除节点没有子节点,则只需将父节点对其引用删除即可
                int childCount = 0;
                if (current.leftNode != null) {
                    childCount++;
                }
                if (current.rightNode != null) {
                    childCount++;
                }
                switch (childCount) {
                    case 0:
                        return deleteNoneChild(parent, current);
                    case 1:
                        return deleteOneChild(parent, current);
                    case 2:
                        return deleteTwoChild(parent, current);
                    default:
                        return false;
                }
            }
        }
    }

    //前序遍历
    public void preOrder(BinaryNode binaryNode) {
        if (binaryNode != null) {
            System.out.println(binaryNode.key);
            preOrder(binaryNode.leftNode);
            preOrder(binaryNode.rightNode);
        }
    }

    //中序遍历
    public void inOrder(BinaryNode binaryNode) {
        if (binaryNode != null) {
            inOrder(binaryNode.leftNode);
            System.out.println(binaryNode.key);
            inOrder(binaryNode.rightNode);
        }
    }

    //后序遍历
    public void postOrder(BinaryNode binaryNode) {
        if (binaryNode != null) {
            inOrder(binaryNode.leftNode);
            inOrder(binaryNode.rightNode);
            System.out.println(binaryNode.key);
        }
    }

    //最小深度
    public int minDepth(BinaryNode binaryNode) {
        if (binaryNode == null) {
            return 0;
        }
        int leftDepth = minDepth(binaryNode);
        int rightDepth = minDepth(binaryNode);
        return Math.min(leftDepth, rightDepth) + 1;
    }

    //最大深度
    public int maxDepth(BinaryNode binaryNode) {
        if (binaryNode == null) {
            return 0;
        }
        int leftDepth = maxDepth(binaryNode);
        int rightDepth = maxDepth(binaryNode);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    //节点总个数
    public int countOfNode(BinaryNode binaryNode) {
        if (binaryNode == null) {
            return 0;
        }
        int leftCount = countOfNode(binaryNode.leftNode);
        int rightCount = countOfNode(binaryNode.rightNode);
        return leftCount + rightCount + 1;
    }

    //叶子节点个数
    public int countOfNoChildNode(BinaryNode binaryNode) {
        if (binaryNode == null) {
            return 1;
        }
        int leftCount = countOfNoChildNode(binaryNode.leftNode);
        int rightCount = countOfNoChildNode(binaryNode.rightNode);
        return leftCount + rightCount;
    }

    //计算第k层的节点个数
    public int countOfLevelNode(BinaryNode binaryNode, int level) {
        if (binaryNode == null || level < 1) {
            return 0;
        }
        if (level == 1) {
            return 1;
        }
        int leftCount = countOfLevelNode(binaryNode.leftNode, level - 1);
        int rightCount = countOfLevelNode(binaryNode.rightNode, level - 1);
        return leftCount + rightCount;
    }

    private boolean deleteNoneChild(BinaryNode parent, BinaryNode binaryNode) {
        if (binaryNode == parent.leftNode) {
            parent.leftNode = null;
        } else {
            parent.rightNode = null;
        }
        return true;
    }

    private boolean deleteOneChild(BinaryNode parent, BinaryNode binaryNode) {
        if (binaryNode == parent.leftNode) {
            parent.leftNode = parent.leftNode != null ? parent.leftNode : parent.rightNode;
        } else {
            parent.rightNode = parent.leftNode != null ? parent.leftNode : parent.rightNode;
        }
        return true;
    }

    private boolean deleteTwoChild(BinaryNode parent, BinaryNode binaryNode) {
        BinaryNode successor = findSuccessor(binaryNode);
        if (binaryNode == parent.leftNode) {
            parent.leftNode = successor;
        } else {
            parent.rightNode = successor;
        }
        return true;
    }

    private BinaryNode findSuccessor(BinaryNode binaryNode) {
        BinaryNode current = binaryNode.rightNode;
        BinaryNode parent = current;
        //如果删除节点的右子节点没有左子节点,则删除节点的右子节点即为后继节点
        if (current.leftNode == null) {
            return current;
        }
        while (current != null) {
            parent = current;
            current = current.leftNode;
        }
        parent.leftNode = current.rightNode;
        current.rightNode = binaryNode.rightNode;
        return current;
    }

}

@NoArgsConstructor
class BinaryNode {
    int key;
    BinaryNode leftNode;
    BinaryNode rightNode;

    public BinaryNode(int key) {
        this.key = key;
    }
}
